Trong khi không được phát hành thương mại, "Underneath the Stars" được tán dương hết lời, trở thành bản thu được đánh giá cao nhất của album, cùng với những khen ngợi đến từ giới phê bình âm nhạc dành cho giọng hát và cách phối nhạc của bài hát. Rolling Stone nói rằng, "Afanasieff đã đồng sáng tác một trong những giai điệu mạnh mẽ nhất của mình, một 'Underneath the Stars' ngọt ngào và đàn hồi."[12] Chris Nickson, tác giả của Mariah Carey Revisited: Her Story (1998), nói rằng bài hát giống như "một bản slow jam tiết tấu mạnh được phát hành trong những năm 90s, và nó mang lại nhiều cảm xúc đêm muộn cùng với những vũ công"[13]. Chris Dickinson của St. Louis Post-Dispatch gọi bài hát là một trong những sáng tác xuất sắc nhất của Carey, ông viết "nó dễ dàng khơi gợi lên một sự khoái lạc mơ hồ uể oải bằng những âm trầm rộn ràng và âm giả thanh điện tử."[14] Cây bút Christopher John Farley của Time mô tả "Underneath the Stars" "tuyệt diệu và bồi hồi hạnh phúc" trong khi Cheo H. Coker gọi bài hát "bùng nổ nhưng tinh tế."[15][16] Bài hát được phát hành với số lượng hạn chế tại Hoa Kỳ, và trụ hạng yếu ớt trên bảng xếp hạng Billboard Hot R&B/Hip-Hop Songs, đạt được vị trí 69.[17]